package 中等.数学;

/**
 * 给定一个整数 n ，返回 n! 结果中尾随零的数量。
 * <p>
 * 提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/factorial-trailing-zeroes/
 */
public class 阶乘后的零_172 {

    public static void main(String[] args) {

        System.out.println(trailingZeroes2(100));

    }

    /**
     * 数学
     * 如果1....n中间有5倍数，那么他会和前面2的倍数相乘增加一个0
     * 2的倍数数量始终比5的倍数数量多，那么5的倍数的数量即为0数量的总和
     * <p>
     * 数字 num 的5的倍数的数量，num/5
     * 而n的阶乘
     * 100的阶乘=100 * 99 * 98 ... * 1
     * 对于100，需要尽可能多的5相乘，分解成5*5*4
     * 多分解出一个5就相当于一个零
     *
     * @param n
     * @return
     */
    public static int trailingZeroes(int n) {
        int ans = 0;
        for (int i = 5; i <= n; i += 5) {  // 只能5的倍数才能除尽5
            int curNum = i;  // 临时变量
            while (curNum > 0 && curNum % 5 == 0) {  // 例如25可以分解成 5*5
                ans++;
                curNum /= 5;
            }
        }
        return ans;
    }

    /**
     * 1*5  2*3  3*5  ...
     * 1*5*5  2*5*5  3*5*5  ...
     * 找规律
     * 每隔5个数会出现1个5
     * 每隔25个数会出现2个5
     * ...
     * 答案为
     * n/5 + n/25 +n/125 +...
     *
     * @param n
     * @return
     */
    public static int trailingZeroes2(int n) {
        int ans = 0;
        while (n > 0) {
            n /= 5;
            ans += n;
        }
        return ans;
    }

}
